Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Dynamic Top- K interesting subgraph query on large-scale labeled graph
SONG Baoyan, JIA Chunjie, SHAN Xiaohuan, DING Linlin, DING Xingyan
Journal of Computer Applications    2018, 38 (2): 471-477.   DOI: 10.11772/j.issn.1001-9081.2017082360
Abstract370)      PDF (1088KB)(423)       Save
The traditional algorithms are difficult to implement the Top- K subgraph query on large-scale dynamic labeled graph due to high time or space complexity. For this reason, a dynamic Top- K interesting subgraph query method named DISQtop- K was proposed. In this algorithm, a Graph Topology Structure Feature (GTSF) index that include Node Topology Feature (NTF) index and Edge Feature (EF) index was established, which can effectively prune and filter the invalid nodes and edges. Then a multi-factor candidate set filtering strategy was put forward based on GTSF index, which can be used to further prune the query graph candidate sets. Considering that the dynamic changes in the graph may have an impact on the matching results, to ensure the real-time and accuracy of the query results, a new matching-verification method for Top- K interesting subgraph was also given, which has two stages of initial matching and dynamic correction. Experimental results show that compared with RAM and RWM, DISQtop- K method costs shorter time for index creation and occupies less space, which can effectively deal with dynamic Top- K interesting subgraph query on large-scale labeled graph.
Reference | Related Articles | Metrics